#ifndef BIMAP_H
#define BIMAP_H

#include <unordered_map>
#include <unordered_set>
#include <optional>


template <typename K, typename V>
class BiMap
{
public:
    // 插入键值对（若key已存在则覆盖）
    void insert(const K& key, const V& value)
    {
        if (m_forwardMap.count(key)) {
            V oldValue = m_forwardMap[key];
            // 删除反向映射中旧的value→key
            auto range = m_reverseMap.equal_range(oldValue);
            for (auto it = range.first; it != range.second; ++it) {
                if (it->second == key) {
                    m_reverseMap.erase(it);
                    break;
                }
            }
        }
        m_forwardMap[key] = value;
        m_reverseMap.insert({value, key});
    }

    // 通过key获取value
    std::optional<V> value(const K& key) const
    {
        auto it = m_forwardMap.find(key);
        if (it != m_forwardMap.end()) {
            return it->second;
        }
        return std::nullopt;
    }

    // 通过value获取所有对应的key
    std::unordered_set<K> keys(const V& value) const
    {
        std::unordered_set<K> keys;
        auto range = m_reverseMap.equal_range(value);
        for (auto it = range.first; it != range.second; ++it) {
            keys.insert(it->second);
        }
        return keys;
    }

    // 删除指定key
    void erase(const K& key)
    {
        auto it = m_forwardMap.find(key);
        if (it == m_forwardMap.end()) {
            return;
        }
        V value = it->second;
        m_forwardMap.erase(it);
        // 删除反向映射中对应的key
        auto range = m_reverseMap.equal_range(value);
        for (auto rit = range.first; rit != range.second; ++rit) {
            if (rit->second == key) {
                m_reverseMap.erase(rit);
                break;
            }
        }
    }
    void clear()
    {
        m_forwardMap = {};
        m_reverseMap = {};
    }
    // 检查key是否存在
    bool containsKey(const K& key) const
    {
        return m_forwardMap.count(key) > 0;
    }

    // 检查value是否存在
    bool containsValue(const V& value) const
    {
        return m_reverseMap.count(value) > 0;
    }
private:
    std::unordered_map<K, V> m_forwardMap;       // 正向映射：key→value（key唯一）
    std::unordered_multimap<V, K> m_reverseMap;  // 反向映射：value→key集合
};

#endif // BIMAP_H
